//
// Created by Snow on 2023/4/9.
//
//广度优先遍历算法
//
//广度优先遍历中使用队列的基本运算算法
//
#include"graph0.cpp"
#define MaxSize 100
typedef int ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;
void InitQueue(SqQueue *&q)
{
    q=(SqQueue*)malloc(sizeof(SqQueue));
    q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q)
{
    free(q);
}
bool QueueEmpty(SqQueue *q)
{
    return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e)
{
    if((q->rear+1)%MaxSize==q->front)
        return false;
    q->rear=(q->rear+1)%MaxSize;
    q->data[q->rear]=e;
    return true;
}
bool deQueue(SqQueue *&q,ElemType &e)
{
    if(q->front==q->rear)
        return false;
    q->front=(q->front+1)%MaxSize;
    e=q->data[q->front];
    return true;
}

void BFS(AdjGraph *G,int v)
{
    int w,i;
    ArcNode *p;
    SqQueue *qu;//定义环形队列指针
    InitQueue(qu);//初始化队列
    int visited[MAXV];//定义顶点访问标志数组
    for(i=0;i<G->n;i++)//访问标志数组初始化
        visited[i]=0;
    printf("%2d",v);//输出被访问顶点的编号
    visited[v]=1;//置已访问标记
    enQueue(qu,v);
    while(!QueueEmpty(qu))
    {
        deQueue(qu,w);//出队一个顶点w
        p=G->adjlist[w].firstarc;//指向w的第一个邻接点
        while(p!=nullptr)
        {
            if(visited[p->adjvex]==0)//若当前邻接点未被访问
            {
                printf("%2d",p->adjvex);//访问该邻接点
                visited[p->adjvex]=1;//置已访问标记
                enQueue(qu,p->adjvex);//该顶点进队
            }
            p=p->nextarc;//找下一个邻接点
        }
    }
    DestroyQueue(qu);
    printf("\n");
}
int main()
{
    AdjGraph *G;
    int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0},
                       {0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};
    int n=5, e=8;
    CreateAdj(G,A,n,e);			//建立《教程》中图8.1(a)的邻接表
    printf("G:\n");
    DispAdj(G);					//输出邻接表G
    printf("BFS:");
    BFS(G,2);
    printf("\n");
    DestroyAdj(G);				//销毁邻接表
    return 0;
}